package com.yoshino.leetcode.oneHundred.seventeenth;

import java.util.ArrayList;
import java.util.List;

class MedianFinder {

    List<Integer> lists;
    /** initialize your data structure here. */
    public MedianFinder() {
        lists = new ArrayList<>();
    }
    
    public void addNum(int num) {
        int ind = 0;
        while (ind < lists.size() && lists.get(ind) < num) {
            ind++;
        }
        lists.add(ind, num);
    }
    
    public double findMedian() {
        int tot = lists.size();
        return tot % 2 == 0 ? (lists.get(tot / 2) + lists.get(tot / 2 - 1)) / 2.0 : lists.get(tot / 2);
    }
}